package 数据结构和算法.链表;

import java.util.Map;
import java.util.TreeMap;

public class RangeList {
    private TreeMap<Integer, Integer> ranges = new TreeMap<>();

    public void add(int left, int right) {
        Map.Entry<Integer, Integer> entry = ranges.higherEntry(left);
        if (entry != ranges.firstEntry()) {
            Map.Entry<Integer, Integer> start = entry != null ? ranges.lowerEntry(entry.getKey()) : ranges.lastEntry();
            if (start != null && start.getValue() >= right) {
                return;
            }
            if (start != null && start.getValue() >= left) {
                left = start.getKey();
                ranges.remove(start.getKey());
            }
        }
        while (entry != null && entry.getKey() <= right) {
            right = Math.max(right, entry.getValue());
            ranges.remove(entry.getKey());
            entry = ranges.higherEntry(entry.getKey());
        }
        ranges.put(left, right);
    }

    public void print() {
        StringBuilder builder = new StringBuilder();
        ranges.forEach((k, v) -> {
            builder.append("[").append(k).append(",").append(v).append("),");
        });
        builder.deleteCharAt(builder.length() - 1);
        System.out.println(builder);
    }

    public void remove(int left, int right) {
        Map.Entry<Integer, Integer> entry = ranges.higherEntry(left);
        if (entry != ranges.firstEntry()) {
            Map.Entry<Integer, Integer> start = entry != null ? ranges.lowerEntry(entry.getKey()) : ranges.lastEntry();
            if (start != null && start.getValue() >= right) {
                int ri = start.getValue();
                if (start.getKey() == left) {
                    ranges.remove(start.getKey());
                } else {
                    ranges.put(start.getKey(), left);
                }
                if (right != ri) {
                    ranges.put(right, ri);
                }
                return;
            } else if (start != null && start.getValue() > left) {
                if (start.getKey() == left) {
                    ranges.remove(start.getKey());
                } else {
                    ranges.put(start.getKey(), left);
                }
            }
        }
        while (entry != null && entry.getKey() < right) {
            if (entry.getValue() <= right) {
                ranges.remove(entry.getKey());
                entry = ranges.higherEntry(entry.getKey());
            } else {
                ranges.put(right, entry.getValue());
                ranges.remove(entry.getKey());
                break;
            }
        }
    }
}